package com.cty._05_Ability._60_DicesProbability;

/**
 * @Auther: cty
 * @Date: 2020/7/24 17:52
 * @Description: 面试题60：n个骰子的点数
 * 题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s
 * 的所有可能的值出现的概率。
 *
 * 递归：从初始情况出发，逐层递归，将所有情况都列出来，再对所有的情况进行统计归类。
 * 循环：从初始情况出发，思考各层结果，根据结果找层与层之间的过程规律，从而写出算法。
 * @version: 1.0
 */
public class DicesProbability {

    private static final int DICES_MAXVALUE = 6;

    /**
     * 方法一：递归实现
     * 缺点：存在重复，时间效率低
     * @param n
     */
    public static void printDicesProbability(int n){
        if(n < 1)
            return;

        int total = (int)Math.pow(DICES_MAXVALUE,n);
        int[] sumNumbers = new int[n*DICES_MAXVALUE - n + 1];
        probability(sumNumbers, n);

        for(int i=0; i<sumNumbers.length; i++)
            System.out.printf("和为 " + (n+i) + " 出现的概率为：%f\n", sumNumbers[i]*1.0/total);
    }  // end printDicesProbability()

    private static void probability(int[] sumNumbers, int n){
        for(int i=1; i<=DICES_MAXVALUE; i++)
            recProbability(sumNumbers,n, i, n);
    }  // end probability()

    private static void recProbability(int[] sunNumbers, int origin, int sum, int kthDicesNTo1){
        if(kthDicesNTo1 == 1)
            sunNumbers[sum-origin]++;
        else {
            for(int i=1; i<=DICES_MAXVALUE; i++)
                recProbability(sunNumbers, origin, sum+i, kthDicesNTo1-1);
        }
    }  // end recProbability()


    /**
     * 方法二：循环实现
     * @param n
     */
    public static void printDicesProbability2(int n){
        if(n < 1)
            return;

        int total = (int)Math.pow(DICES_MAXVALUE,n);
        int[][] probability = new int[2][];
        probability[0] = new int[DICES_MAXVALUE*n + 1];
        probability[1] = new int[DICES_MAXVALUE*n + 1];
        int flag = 0;

        for(int i=1; i<=DICES_MAXVALUE; i++)
            probability[flag][i] = 1;

        for(int i=2; i<=n; i++){
            for(int j=i; j<=DICES_MAXVALUE*i; j++)
                for(int k=j-1; k>=j-DICES_MAXVALUE && k>=1; k--)
                    probability[1-flag][j] += probability[flag][k];
            flag = 1 - flag;
        }

        for(int i=n; i<=DICES_MAXVALUE*n; i++)
            System.out.printf("和为 " + i + " 出现的概率为：%f\n", probability[flag][i]*1.0/total);
    }  // end printDicesProbability2()

}  // end class
